Search results for "Abstract family of languages"

showing 10 items of 14 documents

TWO-DIMENSIONAL FINITE STATE RECOGNIZABILITY

1996

The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with re…

Algebra and Number TheoryString (computer science)Abstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Ontology languagePicture languageCone (formal languages)Theoretical Computer ScienceUndecidable problemAlgebraComputational Theory and MathematicsClosure (mathematics)Regular languageComputer Science::Programming LanguagesComputer Science::Formal Languages and Automata TheoryInformation SystemsMathematicsFundamenta Informaticae
researchProduct

On the Shuffle of Star-Free Languages

2012

Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.

Discrete mathematicsAlgebra and Number TheorySettore INF/01 - Informaticapure submonoidGeneral problemAbstract family of languagesRegular languageComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Star (graph theory)star-free languageCone (formal languages)shuffle of languagePumping lemma for regular languagesTheoretical Computer ScienceCombinatorics on wordsComputational Theory and MathematicsRegular languagecombinatorics on words.Information SystemsMathematicsFundamenta Informaticae
researchProduct

Unary Languages Recognized by Two-Way One-Counter Automata

2014

A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we know little about its power in the case of unary languages. Up to our knowledge, the only known unary nonregular languages recognized by 2D1CAs are those formed by strings having exponential length, where the exponents form some trivial unary regular language. In this paper, we present some non-trivial subsets of these languages. By using the input head as a second counter, we present simulations of two-way deterministic finite automata with linearly bounded counters and linear–space Turing machines. We also show …

Discrete mathematicsCounter machineTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineTheoretical computer scienceUnary operationAbstract family of languagesTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonUnary languageUnary functionComputer Science::Formal Languages and Automata TheoryMathematicsSparse language
researchProduct

On block pumpable languages

2016

Ehrenfeucht, Parikh and Rozenberg gave an interesting characterisation of the regular languages called the block pumping property. When requiring this property only with respect to members of the language but not with respect to nonmembers, one gets the notion of block pumpable languages. It is shown that these block pumpable are a more general concept than regular languages and that they are an interesting notion of their own: they are closed under intersection, union and homomorphism by transducers; they admit multiple pumping; they have either polynomial or exponential growth.

Discrete mathematicsGeneral Computer ScienceAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciences02 engineering and technology01 natural sciencesCone (formal languages)Pumping lemma for regular languagesTheoretical Computer ScienceCombinatoricsRegular languageIntersection010201 computation theory & mathematicsBlock (programming)0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingHomomorphismPumping lemma for context-free languagesComputer Science::Formal Languages and Automata TheoryMathematicsTheoretical Computer Science
researchProduct

Quantum Finite Automata and Logics

2006

The connection between measure once quantum finite automata (MO-QFA) and logic is studied in this paper. The language class recognized by MO-QFA is compared to languages described by the first order logics and modular logics. And the equivalence between languages accepted by MO-QFA and languages described by formulas using Lindstrom quantifier is shown.

Discrete mathematicsLindström quantifierNested wordAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science::Computational ComplexityComputer Science::Digital LibrariesAlgebraTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESMonoidal t-norm logicComputer Science::Programming LanguagesQuantum finite automataEquivalence (formal languages)T-norm fuzzy logicsComputer Science::Formal Languages and Automata TheoryAND gateMathematics
researchProduct

Languages Recognizable by Quantum Finite Automata

2006

There are several nonequivalent definitions of quantum finite automata. Nearly all of them recognize only regular languages but not all regular languages. On the other hand, for all these definitions there is a result showing that there is a language l such that the size of the quantum automaton recognizing L is essentially smaller than the size of the minimal deterministic automaton recognizing L. For most of the definitions of quantum finite automata the problem to describe the class of the languages recognizable by the quantum automata is still open. The partial results are surveyed in this paper. Moreover, for the most popular definition of the QFA, the class of languages recognizable b…

Discrete mathematicsNested wordRegular languageDeterministic automatonProbabilistic automatonQuantum finite automataAbstract family of languagesNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryQuantum computerMathematics
researchProduct

Logics for context-free languages

1995

We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.

Discrete mathematicsRange (mathematics)Class (set theory)Quantifier (logic)Symbol (programming)Context-free languageAbstract family of languagesOrder (group theory)Of the formAlgorithmMathematics
researchProduct

RECOGNIZABLE PICTURE LANGUAGES

1992

The purpose of this paper is to propose a new notion of recognizability for picture (two-dimensional) languages extending the characterization of one-dimensional recognizable languages in terms of local languages and alphabetic mappings. We first introduce the family of local picture languages (denoted by LOC) and, in particular, prove the undecidability of the emptiness problem. Then we define the new family of recognizable picture languages (denoted by REC). We study some combinatorial and language theoretic properties of REC such as ambiguity, closure properties or undecidability results. Finally we compare the family REC with the classical families of languages recognized by four-way a…

Finite-state machinebusiness.industrymedia_common.quotation_subjectClosure (topology)Abstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)AmbiguityOntology languageCone (formal languages)DecidabilityPhilosophy of languageTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESArtificial IntelligenceComputer Science::Programming LanguagesComputer Vision and Pattern RecognitionArtificial intelligencebusinessComputer Science::Formal Languages and Automata TheorySoftwareMathematicsmedia_commonInternational Journal of Pattern Recognition and Artificial Intelligence
researchProduct

Cancellation, pumping and permutation in formal languages

1984

Formal grammarTheoretical computer scienceChomsky hierarchyFormal languageContext-free languageAbstract family of languagesPumping lemma for context-free languagesArithmeticCone (formal languages)Pumping lemma for regular languagesMathematics
researchProduct

Star-free trace languages

1992

Abstract Generalizing a classical result of Schutzenberger to free partially commutative monoids, we prove that the family of star-free trace languages coincides with the family of aperiodic trace languages.

MonoidPure mathematicsGeneral Computer ScienceAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Star (graph theory)Cone (formal languages)Theoretical Computer ScienceTrace (semiology)Aperiodic graphFormal languageComputer Science::Programming LanguagesCommutative propertyMathematicsComputer Science(all)Theoretical Computer Science
researchProduct